#include<bits/stdc++.h>
using namespace std;

// Class T must has operator < (but need not have operator > and ==)
template <class T>
class AVL {
private:
	struct node {
		T val;
		int cnt,h;
		node * son[2];
		#define lson son[0]
		#define rson son[1]
		node(const T & _val, node * _lson, node * _rson, int _cnt = 1, int _h = 0) : val(_val), cnt(_cnt), h(_h) {lson = _lson, rson = _rson;}
	};
	int ht(node * p) const {return p == nullptr ? -1 : p -> h;}
	
	// Clear u and the subtree of u.
	void clear(node *& u) {
		if(u == nullptr) return;
		clear(u -> lson);
		clear(u -> rson);
		delete u;
		u = nullptr;
	}
	
	node * root;
	
	// Update the height of node u.
	inline void update(node *& u) {
		u -> h = max(ht(u -> lson), ht(u -> rson)) + 1;
	}
	
	// Make the left or right son of u take the place of u.
	inline void rotate(node *& u, bool op) {
		node * v = u -> son[op];
		u -> son[op] = v -> son[op^1];
		v -> son[op^1] = u;
		update(u), update(v);
		u = v;
	}
	
	// Balance the AVL Tree by rotating the node, such that the height difference of the two sons is never larger than 1.
	inline void balance(node *& u){
		if (u == nullptr) return;
		if (ht(u -> lson) - ht(u -> rson) > 1) {
			if(ht(u -> lson -> lson) >= ht(u -> lson -> rson))
				rotate(u, 0);
			else
				rotate(u -> lson, 1), rotate(u, 0);
		}
		else if (ht(u -> rson) - ht(u -> lson) > 1) {
			if(ht(u -> rson -> rson) >= ht(u -> rson -> lson))
				rotate(u, 1);
			else
				rotate(u -> rson, 0), rotate(u, 1);
		}
		update(u);
	}
	
	// Insert the number val.
	void insert(const T & val, node *& u) {
		if (u == nullptr) {
			u = new node(val, nullptr, nullptr);
			return;
		}
		if (val < u -> val) insert(val, u -> lson);
		else if (u -> val < val) insert(val, u -> rson);
		else ++u -> cnt;
		
		balance(u);
	}
	
	// Iterate the AVL Tree, and put all the elements into the vector v.
	void to_vector(vector <T> & v, node * u) {
		if (u == nullptr) return;
		to_vector(v, u -> lson);
		for (int i = 0; i < u -> cnt; ++i) v.push_back(u -> val);
		to_vector(v, u -> rson);
	}
	
public:
	AVL(){
		root = nullptr;
	}
	~AVL() {
		clear(root);
	}
	void insert(const T & val) {
		insert(val, root);
	}
	void to_vector(vector <T> & data) {
		to_vector(data, root);
	}
};

template <class T>
void AVL_sort(vector <T> & data){
	AVL <T> t;
	for(int i = 0; i < data.size(); ++i) t.insert(data[i]);
	data.clear();
	t.to_vector(data);
}
